package Demo01;

public class Main {
    public static void main(String[] args) {

    }
}

class Solution {
    public static void main(String[] args) {
        System.out.println(nthUglyNumber(10));
    }

    public static int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int i2 = 1;
        int i3 = 1;
        int i5 = 1;
        for (int i = 2; i <= n; i++) {
            int a = dp[i2] * 2;
            int b = dp[i3] * 3;
            int c = dp[i5] * 5;
            int min = Math.min(Math.min(a, b), c);
            if(min==a) {
                i2++;
            }
            if(min==b) {
                i3++;
            }
            if(min==c) {
                i5++;
            }
            dp[i] = min;
        }
        return dp[n];
    }
//    public static int nthUglyNumber(int n) {
//        int i2 = 1;
//        int i3 = 1;
//        int i5 = 1;
//        int min = 1;
//        for (int i = 2; i <= n; i++) {
//            min = Math.min(Math.min(i2 * 2, i3 * 3), i5 * 5);
//            if (min == i2 * 2) {
//                i2++;
//            }
//            if (min == i3 * 3) {
//                i3++;
//            }
//            if (min == i5 * 5) {
//                i5++;
//            }
//
//        }
//        return min;
//    }
}
